#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define int long long

typedef long long ll;
const int M = 2e5 + 5;
int n, m, e_cnt, eid = 1, heads[M << 1], s, t;
ll dis[M << 1];

struct Edge {
  int v, nxt, w;
  Edge() {}
  Edge(int v, int nxt, int w) : v(v), nxt(nxt), w(w) {}
  inline bool operator<(const Edge &rhs) const { return w < rhs.w; }
} e[M << 4];

inline void add(int u, int v, int w) {
  e[++e_cnt].v = v, e[e_cnt].nxt = heads[u], heads[u] = e_cnt, e[e_cnt].w = w;
}

using pir = std::pair<ll, int>;
std::vector<Edge> vec[M << 1];
std::priority_queue<pir, std::vector<pir>, std::greater<pir> > pq;

signed main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("P6822 [PA2012]Tax.in", "r", stdin);
  freopen("P6822 [PA2012]Tax.out", "w", stdout);
#endif
#endif

  scanf("%lld%lld", &n, &m);
  for (int i = 1, a, b, c; i <= m; ++i) {
    scanf("%lld%lld%lld", &a, &b, &c);
    vec[a].emplace_back(b, ++eid, c);
    vec[b].emplace_back(a, ++eid, c);
  }
  s = 0, t = eid + 1;
  for (auto &i : vec[1]) { add(s, i.nxt, i.w); }
  for (int i = 1; i <= n; ++i) {
    if (vec[i].empty()) continue;
    auto iter = vec[i].begin();
    std::sort(iter, vec[i].end());
    add(iter->nxt ^ 1, iter->nxt, iter->w);
    for (++iter; iter != vec[i].end(); ++iter) {
      add(iter->nxt ^ 1, iter->nxt, iter->w);
      add((iter - 1)->nxt, iter->nxt, iter->w - (iter - 1)->w);
      add(iter->nxt, (iter - 1)->nxt, 0);
    }
  }
  for (auto &i : vec[n]) { add(i.nxt ^ 1, t, i.w); }
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  pq.emplace(0, 0);
  while (!pq.empty()) {
    int u = pq.top().second, d = pq.top().first;
    pq.pop();
    if (d != dis[u]) continue;
    for (int i = heads[u], v; i; i = e[i].nxt) {
      if (dis[v = e[i].v] > dis[u] + e[i].w) {
        dis[v] = dis[u] + e[i].w;
        pq.emplace(dis[v], v);
      }
    }
  }
  printf("%lld", dis[t]);
  return 0;
}